package leetcode_jz_offer;

/**
 * @author 美女
 * @date 2022/08/31 11:01
 **/

import java.util.ArrayList;
import java.util.List;

/**
 * 滑动窗口（本题是连续正数序列12345...,实际任意递增序列都能适用）
 */
public class Num57_II_和为s的连续正数序列 {
    public static int[][] findContinuousSequence(int target) {
        int left=1;//滑动窗口左边界
        int right=1;//滑动窗口右边界
        int sum=0;
        List<int[]> ret = new ArrayList<>();
        while (left<=target/2){//5最大只能是2+3不能是3+4,取到target的一半即可，因为顺序，3及后面的大数不可能组成5,左边界无需取到>target/2的数
            if(sum<target){
                sum+=right;
                right++;
            }else if(sum>target){
                sum-=left;
                left++;
            }else {
                int[] temp=new int[right-left];//不能取到right，因为sum等于+=right完了等于目标值后right还会++一次
                for (int i = left; i < right; i++) {
                    temp[i-left]=i;
                }
                ret.add(temp);
                //遍历完继续左边界右移,去掉左边移除都元素的值
                sum-=left;
                left++;
            }
        }
        return ret.toArray(new int[ret.size()][]);//链表转化为数组
    }

    public static void main(String[] args) {
        findContinuousSequence(5);
    }
}